package com.wwz.leetcode;

import org.junit.Test;

public class LeetCode45 {

//    public int jump(int[] nums) {
//
//        int jumpCount = 0;
//        df(nums, nums[0], jumpCount);
//
//    }

//    public int df(int[] nums, int num, int jumpCount) {
//        for (int i = 1; i <= num; i++) {
//            jumpCount++;
//            if(jumpCount == nums.length -1){
//                return jumpCount;
//            }
//            df(nums,nums[i],jumpCount);
//        }
//
//    }

    public int jump(int[] nums) {
        int length = nums.length;
        // 上次跳跃可达范围右边界（下次的最右起跳点）
        int end = 0;
        // 可到达的最远位置
        int maxPosition = 0;
        // 跳跃次数
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    @Test
    public void test() {
        System.out.println(jump(new int[]{2, 3, 1, 4, 0, 1}));

    }
}
